package com.suanfa.jiaoheng;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 核心思想是反向思考，最短路径中的每个节点到起始节点都是最短路径
 *      在找到目标节点为止，保存每个节点到起始节点的最短路径
 *
 *      图中的环会导致算法失效？有循环怎么判断？
 *
 *
 */
public class 第7课迪杰斯特拉 {


    public static void main(String[] args) {
        Node startNode = 创造线路();
        迪杰斯特拉算法(startNode,"稻香湖路");
    }

    // 定义图中的结点
    static class Node{
        String name;
        // 此节点到起始节点的最短距离，默认Integer最大值
        Integer distance = Integer.MAX_VALUE;
        // 此节点到起始节点最短距离的上一个节点
        Node lastNode;
        List<WeightEdge> toWeightEdgeList = new ArrayList<>();
    }

    static class WeightEdge{
        Node toNode;
        Integer weight;

        public WeightEdge(Node toNode, Integer weight) {
            this.toNode = toNode;
            this.weight = weight;
        }
    }

    /**
     *
     * 呼家楼，白石桥南，国家图书馆，稻香湖路
     * 呼家楼，海淀黄庄，西苑，稻香湖路
     * 呼家楼，二里沟，稻香湖路
     */
    static Node 创造线路(){
        Node startNode = new Node();
        startNode.name = "呼家楼";

        Node 白石桥南 = new Node();
        白石桥南.name = "白石桥南";

        Node 国家图书馆 = new Node();
        国家图书馆.name = "国家图书馆";

        Node 稻香湖路 = new Node();
        稻香湖路.name = "稻香湖路";

        Node 二里沟 = new Node();
        二里沟.name = "二里沟";

        Node 海淀黄庄 = new Node();
        海淀黄庄.name = "海淀黄庄";

        Node 西苑 = new Node();
        西苑.name = "西苑";

        // 开始设置其list
        startNode.toWeightEdgeList.add(new WeightEdge(白石桥南,1));
        startNode.toWeightEdgeList.add(new WeightEdge(海淀黄庄,1));
        startNode.toWeightEdgeList.add(new WeightEdge(二里沟,1));

        白石桥南.toWeightEdgeList.add(new WeightEdge(国家图书馆,1));
        国家图书馆.toWeightEdgeList.add(new WeightEdge(稻香湖路,1));

        海淀黄庄.toWeightEdgeList.add(new WeightEdge(西苑,1));
        西苑.toWeightEdgeList.add(new WeightEdge(稻香湖路,1));

        二里沟.toWeightEdgeList.add(new WeightEdge(稻香湖路,1));

        return startNode;
    }

    static void 迪杰斯特拉算法(Node startNode,String targetNodeName){
        Map<String,Integer> nodeDistanceMap = new HashMap<>();

        Set<WeightEdge> haveChecked = new HashSet<>();
        Queue<Node> checkQueue = new LinkedBlockingQueue<>();

        checkQueue.add(startNode);

        startNode.distance = 0;
        nodeDistanceMap.put(startNode.name,startNode.distance);

        Node currentNode = null;
        // 这里再加一个targetNode的查询吧，查到后使用参数带出来
        Node targetNode = null;
        while(!checkQueue.isEmpty()){
            currentNode = checkQueue.poll();
            if(currentNode.name.equals(targetNodeName)){
                targetNode = currentNode;
            }

            // 这里是核心逻辑，更新边对应的节点距离初始节点的距离
            for(WeightEdge toWeightEdge : currentNode.toWeightEdgeList){
                // 这一步好像就对应的网上写的这个算法的标识节点是否处理过吧,熟悉后再回过来看
                // 这里改成如果这条边处理过，就不再处理了试试
                if(haveChecked.contains(toWeightEdge)){
                    continue;
                }
                haveChecked.add(toWeightEdge);

                // 添加要处理的节点到队列
                checkQueue.add(toWeightEdge.toNode);
                // 更新对应节点距离初始节点的距离
                Integer newDistance = currentNode.distance+toWeightEdge.weight;
                if(nodeDistanceMap.get(toWeightEdge.toNode.name)==null
                        || nodeDistanceMap.get(toWeightEdge.toNode.name) > newDistance){
                    toWeightEdge.toNode.distance = newDistance;
                    toWeightEdge.toNode.lastNode = currentNode;
                    nodeDistanceMap.put(toWeightEdge.toNode.name,newDistance);
                }
            }

        }
        // 打印一下距离
        for (Map.Entry<String, Integer> stringIntegerEntry : nodeDistanceMap.entrySet()) {
            System.out.println(stringIntegerEntry.getKey()+ "距离初始节点距离为:"+stringIntegerEntry.getValue());
        }

        // 打印下到稻香湖的最短距离
        Stack stack = new Stack<>();
        stack.push(targetNodeName);
        Node lastNode = targetNode;

        while(lastNode.lastNode!=null){
            lastNode = lastNode.lastNode;
            stack.push(lastNode.name);
        }

        while(!stack.empty()){
            System.out.print(stack.pop()+"-->");
        }
    }
}
